Lists

List literals

A list with a constant length can be written by closing the list elements in brackets and separating the elements by commas:

[1,2,3]
[]

Range literals produce a sequence of consecutive integers:

[4..8]      -- [4, 5, 6, 7, 8]
[1..5]      -- [1, 2, 3, 4, 5]

List comprehension

Lists can be formed with list comprehension expressions that resemble set comprehension in mathematics. For example

[x+1 | x <- lst]

creates a list of all elements in lst increased by one and

[x+y | x <- lstX, y <- lstY]

creates list of all sums of pairs where one element is in lstX and one in lstY. Note that the list may contain duplicates.

It is possible to add also constraints

[x `div` 2 | x <- lst, x `mod` 2 == 0]

and definitions

[x*y | x <- lst, y = x+1]

Formally, a list comprehension expression is

[<expression> | <list qualifier>, ..., <list qualifier>]

where list qualifier can be one of the following

  • generator <variable> <- <list expression>
  • guard <boolean>
  • definition <variable> = <expression>
  • then <expression> by <expression>

The last type of qualifier can be used to make operations that affect the whole list. For example

then drop 3

removes the first three elements and

then sortBy by x

sorts the elements by field x (where x is a definition in the qualifier). The general form is then <transform-function> by <key-function>, where by is optional for transforms that do not need a key (e.g. then drop 3, then reverse).

Accessing the list elements

The most basic way of reading list is to read it element by element.

(!) :: IndexedSequence a => a b -> Integer -> b (Prelude)

seq ! i returns the ith element of the sequence seq. Indexing starts from zero.

length :: Sequence a => a -> Integer (Prelude)

Length of the sequence

Comparison

Lists like almost all other types support the generic equality and comparison operations:

Didn't find the value '=='.
(!=) :: a -> a -> Boolean (Prelude)
(<) :: Ord a => a -> a -> Boolean (Prelude)

Less

(<=) :: Ord a => a -> a -> Boolean (Prelude)

Less or equal

(>) :: Ord a => a -> a -> Boolean (Prelude)

Greater

(>=) :: Ord a => a -> a -> Boolean (Prelude)

Greater or equal

For example lst == [] tests whether the lst is empty. The comparison of the list is lexicographic.

Executing code for each list element

The only difference between the following iteration functions is the order of their parameters:

iter :: FunctorE a => (b -> <d> c) -> a b -> <d> () (Prelude)

Calls the given function with all elements of the given container.

for :: FunctorE a => a b -> (b -> <d> c) -> <d> () (Prelude)

Iterates the elements of the given collection. Same as iter but parameters flipped.

When the loop body needs the element's index as well as its value, use the indexed variants:

iterI :: FunctorE a => (Integer -> b -> <d> c) -> a b -> <d> () (Prelude)

Calls the given function with all elements of the given container giving also the index of the element as a parameter.

forI :: FunctorE a => a b -> (Integer -> b -> <d> c) -> <d> () (Prelude)

Iterates the elements of the given collection providing also the indices of the elements. Same as iterI but parameters flipped.

To iterate a fixed number of times (without a list), use:

forN :: Integer -> (Integer -> <b> a) -> <b> () (Prelude)

forN n f calls f for all integers 0, ..., n-1

Concatenating lists

(+) :: Additive a => a -> a -> a (Prelude)

Adds two objects (numbers, vectors, strings, etc.) together.

sum :: Additive a => [a] -> a (Prelude)

Sum of the elements:

sum [e1,e2,...,eN] = e1 + e2 + ... + eN

Implemented usually more efficiently than with repetitive application of (+).

List transformations

map :: FunctorE a => (b -> <d> c) -> a b -> <d> a c (Prelude)

Applies the function to all elements of the container and returns the similarly shaped container with the results:

For lists,

map f [e1, e2, ..., eN] = [f e1, f e2, ..., f eN]

for example

map (*2) [1..5] = [2, 4, 6, 8, 10]
filter :: MonadZeroE a => (b -> <c> Boolean) -> a b -> <c> a b (Prelude)
partition :: (a -> <b> Boolean) -> [a] -> <b> ([a], [a]) (Prelude)
join :: Monad a => a (a b) -> a b (Prelude)

The join function is the conventional monad join operator. It removes one level of monadic structure.

For lists, join concatenates a list of lists:

join [[1,2], [3,4]] = [1, 2, 3, 4]
concatMap :: (a -> <c> [b]) -> [a] -> <c> [b] (Prelude)

concatMap combines map and join functions. It maps the elements of a given list to lists with the given function and concatenates the results.

concatMap f lst = join (map f lst) = [y | x <- lst, y <- f x]
mapMaybe :: (a -> <c> Maybe b) -> [a] -> <c> [b] (Prelude)

mapMaybe combines map and filter functions. It applies the given function to every element of the input list. If the result is Just x, then x is added to the resulting list.

mapMaybe f lst = [y | x <- lst, Just y = f x]
zip :: [a] -> [b] -> [(a, b)] (Prelude)

Combines two lists into one list of pairs. The length of the resulting list is the length of the smallest input list.

zip [1, 2, 3, 4, 5] ['a', 'b', 'c'] = [(1, 'a'), (2, 'b'), (3, 'c')]
zipWith :: (a -> b -> <d> c) -> [a] -> [b] -> <d> [c] (Prelude)

Combines two lists by using the given function for combining the elements. The length of the resulting list is the length of the smallest input list.

unzip :: [(a, b)] -> ([a], [b]) (Prelude)

Produces two lists from one list of pairs.

unzip [(1, 'a'), (2, 'b'), (3, 'c')] = ([1, 2, 3], ['a', 'b', 'c'])

Ordering

The following functions modify the order of the list elements:

sort :: Ord a => [a] -> [a] (Prelude)

Sorts the given list using its default order.

sortBy :: Ord a => (b -> <c> a) -> [b] -> <c> [b] (Prelude)

Sorts the lists by the values computed by the first function. For example

sortBy snd [(1,5), (2,3), (3,4)] = [(2,3), (3,4), (1,5)]
sortWith :: (a -> a -> <b> Integer) -> [a] -> <b> [a] (Prelude)

Sorts the list using the given comparator.

reverse :: [a] -> [a] (Prelude)

Reverses a given list. For example, reverse [1,2,3] = [3,2,1]

Sublists

The following functions extract some sublist of the given list:

take :: Sequence a => Integer -> a -> a (Prelude)

take n s returns the first n elements of the sequence s.

drop :: Sequence a => Integer -> a -> a (Prelude)

drop n s removes the first n elements of the sequence s.

sub :: Sequence a => a -> Integer -> Integer -> a (Prelude)

sub s begin end returns a subsequence of s starting from index begin and ending just before index end.

takeWhile :: (a -> <b> Boolean) -> [a] -> <b> [a] (Prelude)

takeWhile p l, returns the longest prefix (possibly empty) of list l of elements that satisfy p

first :: [a] -> a (Prelude)

Returns the first element of a sequence

last :: [a] -> a (Prelude)

Returns the last element of a sequence

Aggregate operations

Sometimes it is necessary to compute some kind of summary over all elements of a list. The most useful generic aggregate operation is foldl.

foldl :: (a -> b -> <c> a) -> a -> [b] -> <c> a (Prelude)
foldl op initialValue list

applies a binary operator op to all elements of list from left to right starting with initialValue. For example,

foldl op init [x1, x2, x3, x4] = (((init `op` x1) `op` x2) `op` x3) `op` x4

It is used to define many more specialized aggreate operations such as

sum     = foldl (+) 0
product = foldl (*) 1
maximum = foldl1 max

There is a variant that traverses the list from right to left:

foldr :: (a -> b -> <c> b) -> b -> [a] -> <c> b (Prelude)

foldr is defined like foldl but it process the list from right to left.

and a variant that that assumes that the list has at least one element:

foldl1 :: (a -> a -> <b> a) -> [a] -> <b> a (Prelude)

Like foldl but assumes that the list is non-empty so the initial is not needed.

scanl is like foldl but returns a list of all intermediate accumulator values instead of only the final result:

scanl :: (a -> b -> <c> a) -> a -> [b] -> <c> [a] (Prelude)

Set-like operations

unique :: [a] -> [a] (Prelude)

Removes duplicates (all but the first occurrence) from the list but otherwise preserves the order of the elements.

uniqueBy :: (a -> <c> b) -> [a] -> <c> [a] (Prelude)

Like unique, but uses the given function for finding the key values used for uniqueness testing.

intersect :: [a] -> [a] -> [a] (Prelude)

Computes a list that contains only elements that belongs to both input lists.

The (\\) operator computes the list difference (removes elements of the second list from the first):

(\\) :: [a] -> [a] -> [a] (Prelude)

a \\ b removes all elements of b from the list a.

Lookup and indexing

lookup performs a linear scan of an association list:

lookup :: a -> [(a, b)] -> Maybe b (Prelude)

Tries to find the given key from the list of key-value pairs and returns the corresponding value.

For repeated lookups it is more efficient to build a hash-map first:

index :: [(a, b)] -> a -> Maybe b (Prelude)

Given a list of key-value pairs, the function produces a function that finds a value efficiently for the given key.

indexBy :: (a -> <c> b) -> [a] -> <c> b -> Maybe a (Prelude)

Given a list of values and a function computing a key for each value, the function produces a function that finds a value effeciently for the given key.

indexGroup :: [(a, b)] -> a -> [b] (Prelude)

Composition of index and group.

indexGroupBy :: (a -> <c> b) -> [a] -> <c> b -> [a] (Prelude)

Composition of index and groupBy.